#include<bits/stdc++.h>
using namespace std;
const int N = 1e3+10;
vector<int> bian[N];
vector<int> res[N];
int centp[N];
int cur;
int n,B;
void merge(vector<int> &v1,vector<int> &v2){
    if(v1.size() > v2.size()){
        swap(v1,v2);
    }
    for(int v: v1){
        v2.push_back(v);
    }
    v1.clear();
}
vector<int> dfs(int x,int fa){
    vector<int> S;
    for(int v : bian[x]){
        if(v == fa){
            continue;
        }
        vector<int> S1 = dfs(v,x);
        merge(S1,S);
        if(S.size() >= B){
            int now = ++cur;
            res[now] = S;
            centp[now] = x;
            S.clear();
        }
    }
    S.push_back(x);
    if(S.size() >= B){
        int now = ++cur;
        res[now] = S;
        centp[now] = x;
        S.clear();
    }
    
    return S;
}
int col[N];
int main(){
    cin>>n>>B;
    for(int i = 1;i<n;i++){
        int u,v;
        cin>>u>>v;
        bian[u].push_back(v);
        bian[v].push_back(u);
    }
    vector<int> es = dfs(1,0);
    merge(es,res[cur]);
    centp[cur] = 1;
    cout<<cur<<'\n';
    for(int i = 1;i<=cur;i++){
        for(int v : res[i]){
            col[v] = i;
        }
    }
    for(int i = 1;i<=n;i++){
        cout<<col[i]<<' ';
    }
    cout<<'\n';
    for(int i = 1;i<=cur;i++){
        cout<<centp[i]<<' ';
    }
    cout<<'\n';
}